package sorting;

import util.ArrayUtil;
import util.Tracer;

public class AverageSort {
	public static void sort(float[] numbers, int k)
	{
		int length = numbers.length;
		int dev = length / k;
		int mod = length % k;
		
		for(int i = 0; i < k; i ++)
		{
			averageSort(numbers, k, i, 0, i > mod ? dev : (dev - 1));
		}
	}
	
	public static void averageSort(float[] numbers, int k, int mod, int p, int r)
	{
		if(p >= r)
			return;
		
		int part = averagePartition(numbers, k, mod, p, r);
		averagePartition(numbers, k, mod, p, part - 1);
		averagePartition(numbers, k, mod, part + 1, r);
	}
	
	public static int averagePartition(float[] numbers, int k, int mod, int p, int r)
	{
		int tail = getRealIndex(r, k, mod);
		float number = numbers[tail];
		
		int part = p;
		for(int i = p; i < r; i ++)
		{
			int ii = getRealIndex(i, k, mod);
			if(numbers[ii] < number)
			{
				ArrayUtil.each(numbers, ii, getRealIndex(part, k, mod));
				part ++;
			}
		}
		
		ArrayUtil.each(numbers, getRealIndex(part, k, mod), tail);
		return part;
	}
	
	private static int getRealIndex(int PIndex, int k, int mod)
	{
		return PIndex * k + mod;
	}
	
	public static void main(String[] args) {
		float[] numbers = new float[]{
			 8, 1, 2, 10, 3, 5, 4,  9, 6
		};
		
		sort(numbers, 2);
		Tracer.trace(numbers);
	}
}
